#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

class SplayTreeNode:
    '''
    用不到双旋, 只用递归左旋或者右旋即可.
    '''
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left, self.right = left, right
        self.cnt = 1

    def search(self, val):
        # splay tree的关键所在, 每次搜索到后, 要把值调节到树根.
        if val == self.val:
            return self

        if val < self.val:
            searched_left = self._search(self.left, val)
            if searched_left is None:
                return None
            else:
                assert searched_left.val == val
                self.left = searched_left
                return self.rotate_left_left()
        else:
            searched_right = self._search(self.right, val)
            if searched_right is None:
                return None
            else:
                assert searched_right.val == val
                self.right = searched_right
                return self.rotate_right_right()

    def _search(self, node, val):
        if node is None:
            return None
        return node.search(val)

    def insert(self, val):
        # print(val, self.val)
        if val == self.val:
            self.cnt += 1
            return

        if val < self.val:
            if self.left is None:
                self.left = SplayTreeNode(val)
            else:
                return self.left.insert(val)
        else:
            if self.right is None:
                self.right = SplayTreeNode(val)
            else:
                return self.right.insert(val)

    def rotate_left_left(self):
        new_root = self.left
        self.left = new_root.right
        new_root.right = self
        return new_root

    def rotate_right_right(self):
        new_root = self.right
        self.right = new_root.left
        new_root.left = self
        return new_root

    def rec_show(self):
        if self.left:
            self.left.rec_show()

        print(self.val, end=" ")

        if self.right:
            self.right.rec_show()


class SplayTree:
    def __init__(self):
        self.root = None

    def insert(self, val):
        if self.root is None:
            self.root = SplayTreeNode(val)
        else:
            self.root.insert(val)

    def search(self, val):
        if self.root is None:
            return None

        if self.root.val == val:
            return self.root

        self.root = self.root.search(val)
        return self.root

    def show(self):
        if self.root is not None:
            self.root.rec_show()
        print('\n===================  =====================')

    def level_show(self):
        pass


def test_splay_tree():
    t = SplayTree()
    for i in range(10):
        t.insert(i)

    print('root %s' % t.root.val)
    t.show()

    t.search(5)
    print('root %s' % t.root.val)
    print('root.left %s' % t.root.left.val)
    print('root.left.r  %s' % t.root.left.right.val)
    # print('root.left.rr %s' % t.root.left.right.right.val)
    print('root.right %s' % t.root.right.val)
    # print('root.right.r %s' % t.root.right.right.val)
    # print('root.right.rr %s' % t.root.right.right.right.val)
    t.show()

    t.search(6)
    t.search(0)
    print('root %s' % t.root.val)
    # print('root.left %s' % t.root.left.val)
    # print('root.left.r  %s' % t.root.left.right.val)
    print('root.right %s' % t.root.right.val)
    print('root.right.r %s' % t.root.right.right.val)
    print('root.right.l %s' % t.root.right.left.val)
    t.show()

    l = list(range(10))
    import random
    random.shuffle(l)

    for i in l:
        t.search(i)
    print('root %s' % t.root.val)
    t.show()

    for i in l:
        t.search(i)
    t.show()
    print('root %s' % t.root.val)



def main():
    print("start main")
    test_splay_tree()

if __name__ == "__main__":
    main()
